{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Bitwise OR of All Subsequence Sums"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #brainteaser #array #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #脑筋急转弯 #数组 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: subsequenceSumOr"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #所有子序列和的按位或"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code> ，返回对数组中所有可能的 <strong>子序列</strong> 之和进行按位 <strong>或</strong> 运算后得到的值。</p>\n",
    "\n",
    "<p>数组的<strong> 子序列 </strong>是从数组中删除零个或多个元素且不改变剩余元素的顺序得到的序列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp;1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [2,1,0,3]\n",
    "<b>输出：</b>7\n",
    "<strong>解释：</strong>所有可能的子序列的和包括：0、1、2、3、4、5、6 。\n",
    "由于 0 OR 1 OR 2 OR 3 OR 4 OR 5 OR 6 = 7，所以返回 7 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [0,0,0]\n",
    "<b>输出：</b>0\n",
    "<strong>解释：</strong>0 是唯一可能的子序列的和，所以返回 0 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [bitwise-or-of-all-subsequence-sums](https://leetcode.cn/problems/bitwise-or-of-all-subsequence-sums/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [bitwise-or-of-all-subsequence-sums](https://leetcode.cn/problems/bitwise-or-of-all-subsequence-sums/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,1,0,3]', '[0,0,0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsequenceSumOr(self, a: List[int]) -> int:\n",
    "        ans = pre = 0\n",
    "        for j in a:\n",
    "            pre += j\n",
    "            ans |= (j|pre)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsequenceSumOr(self, nums: List[int]) -> int:\n",
    "        cur = 0\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            cur += num\n",
    "            ans |= num | cur\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsequenceSumOr(self, nums: List[int]) -> int:\n",
    "        ans=pre=0\n",
    "        for num in nums:\n",
    "            pre+=num\n",
    "            ans|=pre|num\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsequenceSumOr(self, nums: List[int]) -> int:\n",
    "        ans = prefix = 0 \n",
    "        for x in nums: \n",
    "            prefix += x\n",
    "            ans |= x | prefix \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsequenceSumOr(self, nums: List[int]) -> int:\n",
    "        ans=pre=0\n",
    "        for num in nums:\n",
    "            pre+=num\n",
    "            ans|=pre|num\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsequenceSumOr(self, nums: List[int]) -> int:\n",
    "        \n",
    "        cur = 0\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            cur+=num\n",
    "            ans|=num|cur\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsequenceSumOr(self, nums: List[int]) -> int:\n",
    "        cnt = [0] * 63\n",
    "        for x in nums:\n",
    "            for i in range(30):\n",
    "                cnt[i] += x >> i & 1\n",
    "        ans = 0\n",
    "        for i in range(62):\n",
    "            if cnt[i]:\n",
    "                ans |= 1 << i\n",
    "            cnt[i+1] += cnt[i] // 2\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsequenceSumOr(self, nums: List[int]) -> int:\n",
    "        ans = f = i = 0\n",
    "        while i < 32 or f:\n",
    "            cnt = f\n",
    "            if i < 32: \n",
    "                for v in nums:\n",
    "                    cnt += v >> i & 1\n",
    "            f = cnt // 2\n",
    "            if (cnt > 0):\n",
    "                ans |= 1 << i\n",
    "            i += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsequenceSumOr(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 1: return nums[0]\n",
    "        if sum(nums) == 0: return 0\n",
    "        nums.sort()\n",
    "        s = 0\n",
    "        for n in nums:\n",
    "            s |= n\n",
    "        p = 0\n",
    "        while s & 1 == 0:\n",
    "            s >>= 1\n",
    "            p += 1\n",
    "        return (1 << (int(log(sum(nums)) / log(2)) + 1)) - (1 << p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsequenceSumOr(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        pre = 0\n",
    "        for n in nums:\n",
    "            pre += n\n",
    "            res |= pre | n\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsequenceSumOr(self, nums: List[int]) -> int:\n",
    "\n",
    "        cur = 0\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            cur+=num\n",
    "            ans|=num|cur\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsequenceSumOr(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for x in nums:\n",
    "            ans |= x\n",
    "        for x in accumulate(nums):\n",
    "            ans |= x\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsequenceSumOr(self, nums: List[int]) -> int:\n",
    "        c = [0]*63\n",
    "        for x in nums:\n",
    "            for i in range(30):\n",
    "                c[i] += x>>i&1\n",
    "        ans = 0\n",
    "        for i in range(62):\n",
    "            if c[i]:\n",
    "                ans |= 1<<i \n",
    "            c[i+1] += c[i]//2 \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsequenceSumOr(self, nums: List[int]) -> int:\n",
    "        #子序列不改变顺序\n",
    "        prefix=0\n",
    "        ans=0\n",
    "        for x in nums:\n",
    "            #计算前缀和(前k个元素和)\n",
    "            prefix+=x\n",
    "            #所有输入数字、以及输入数字的所有前缀和的 or\n",
    "            ans|=x|prefix\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsequenceSumOr(self, nums: List[int]) -> int:\n",
    "        s = sum(nums)\n",
    "        if s == 0:\n",
    "            return 0\n",
    "        HIGH_BIT = s.bit_length() - 1\n",
    "        ans = 1 << HIGH_BIT\n",
    "        for i in range(HIGH_BIT):\n",
    "            tmp = 0\n",
    "            test = (1 << (i + 1)) - 1\n",
    "            for x in nums:\n",
    "                tmp += x & test \n",
    "                if tmp >= 1 << i:\n",
    "                    ans |= 1 << i \n",
    "                    break \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def subsequenceSumOr(self, nums: List[int]) -> int:\n",
    "        lst = [0] * 64\n",
    "        for num in nums:\n",
    "            for index, digit in enumerate(bin(num)[2:][::-1]):\n",
    "                if digit == '1':\n",
    "                    lst[index] += 1\n",
    "        cur = 1\n",
    "        res = 0\n",
    "        for i in range(63):\n",
    "            if lst[i] > 0:\n",
    "                res += cur\n",
    "            cur *= 2\n",
    "            lst[i + 1] += lst[i] // 2\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def subsequenceSumOr(self, nums: List[int]) -> int:\r\n",
    "        lst = [0] * 64\r\n",
    "        for num in nums:\r\n",
    "            for index, digit in enumerate(bin(num)[2:][::-1]):\r\n",
    "                if digit == '1':\r\n",
    "                    lst[index] += 1\r\n",
    "        cur = 1\r\n",
    "        res = 0\r\n",
    "        for i in range(63):\r\n",
    "            if lst[i] > 0:\r\n",
    "                res += cur\r\n",
    "            cur *= 2\r\n",
    "            lst[i + 1] += lst[i] // 2\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsequenceSumOr(self, nums: List[int]) -> int:\n",
    "        mp = defaultdict(int)\n",
    "        for x in nums:\n",
    "            for i, c in enumerate(bin(x)[2:][::-1]):\n",
    "                if c == '1':\n",
    "                    mp[i] += 1\n",
    "        res = []\n",
    "        for i in range(100):\n",
    "            if mp[i] == 0:\n",
    "                res.append('0')\n",
    "            else:\n",
    "                res.append('1')\n",
    "                mp[i + 1] += mp[i] // 2\n",
    "        return int(''.join(res[::-1]), 2)\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
